package bishi.day25_5_23;

import java.util.Scanner;

/**
 * 星际密码
 *
 * @author 是阿秋啊
 * @date 2022/05/24 11:04
 **/
public class xing_ji_mi_ma {
    public static void main(String[] args) {
        int[] fired = new int[10001];
        fired[1] = 1;
        fired[2] = 2;
        for (int i = 3; i < 10001; i++) {
            fired[i] = fired[i - 1] + fired[i - 2];
            fired[i] = fired[i] % 10000;
        }
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            int n = sc.nextInt();
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < n; i++) {
                int x = sc.nextInt();
                sb.append(String.format("%04d",fired[x]));
            }
            System.out.println(sb);
        }
    }
}